#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    void helper(vector<vector<int>> &res, vector<int> &temp, vector<pair<int, int>> &nums, int pos, int rest)
    {
        if (rest == 0)
        {
            res.push_back(temp);
            return;
        }
        // 优化边界条件(剪枝)
        if (pos >= nums.size() || rest < nums[pos].first)
            return;
        helper(res, temp, nums, pos + 1, rest);
        // 优化选择次数
        int times = min(rest / nums[pos].first, nums[pos].second);
        // 选择n次
        for (int i = 1; i <= times; i++)
        {
            temp.push_back(nums[pos].first);
            helper(res, temp, nums, pos + 1, rest - i * nums[pos].first);
        }
        // 恢复现场
        for (int i = 0; i < times; i++)
            temp.pop_back();
    }
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<vector<int>> res;
        vector<pair<int, int>> nums;
        vector<int> temp;
        // 排序
        sort(candidates.begin(), candidates.end());
        // 统计次数
        for (auto e : candidates)
        {
            if (nums.empty() || e != nums.back().first)
                nums.push_back({e, 1});
            else
                nums.back().second++;
        }
        helper(res, temp, nums, 0, target);
        return res;
    }
};